﻿namespace Algo.Sort
{
    using System.Collections.Generic;
    using System.Linq;

    using JetBrains.Annotations;

    internal sealed class TreeSortStrategy : ISortStrategy
    {
        public IEnumerable<T> Sort<T>(IEnumerable<T> items, IComparer<T> comparer, IAlgoExtensions extensions)
        {
            Node<T> root = null;
            var iterationsCount = 0;
            try
            {
                foreach (var item in items)
                {
                    if (root == null)
                    {
                        root = new Node<T> { Value = item };
                        continue;
                    }

                    var node = root;
                    var inserted = false;
                    do
                    {
                        if (SortUtilities.IsGreaterThen(comparer, node.Value, item))
                        {
                            var leftNode = node.Left;
                            if (leftNode == null)
                            {
                                node.Left = new Node<T> { Value = item };
                                inserted = true;
                            }
                            else
                            {
                                node = leftNode;
                            }
                        }
                        else
                        {
                            var rightNode = node.Right;
                            if (rightNode == null)
                            {
                                node.Right = new Node<T> { Value = item };
                                inserted = true;
                            }
                            else
                            {
                                node = rightNode;
                            }
                        }

                        iterationsCount++;
                    }
                    while (!inserted);
                }
            }
            finally
            {
                IMetricsExtension metricsBehaviour;
                if (extensions.TryGet(out metricsBehaviour))
                {
                    metricsBehaviour.RegisterIterations(iterationsCount);
                }
            }

            return root != null ? IterateItems(root).ToArray() : Enumerable.Empty<T>();
        }

        private static IEnumerable<T> IterateItems<T>(Node<T> parent)
        {
            var leftNode = parent.Left;
            if (leftNode != null)
            {
                foreach (var item in IterateItems(leftNode))
                {
                    yield return item;
                }
            }

            yield return parent.Value;

            var rightNode = parent.Right;
            if (rightNode != null)
            {
                foreach (var item in IterateItems(rightNode))
                {
                    yield return item;
                }
            }
        }

        private class Node<T>
        {
            public T Value { get; set; }

            public Node<T> Left { [CanBeNull] get; set; }

            public Node<T> Right { [CanBeNull] get; set; }
        }
    }
}
